package sort;

import java.util.Arrays;
import java.util.Scanner;
/**
 * @ClassName: quick
 * @Auther: Drawin
 * @Date: 2021/9/20 21:18
 * @Description:
 */

public class quick {
    public static void main(String[] args) {
        System.out.println("请输入数组的个数：");
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
        int[] a= new int[n];
        for(int i=0;i<a.length;i++){
            a[i]=s.nextInt();
        }
        sort(a,0,a.length-1);
        System.out.println(Arrays.toString(a));
    }
    public static void sort(int[]a,int low,int hight){
        int i,j,index,t;
        if(low>hight){
            return;
        }
        i=low;
        j=hight;
        index=a[i];//初基准
        while(i<j){
            while(i<j&&index<=a[j])
                j--;
            if(i<j)
                a[i++]=a[j];//低位替换
            while(i<j&&index>a[i])
                i++;
            if(i<j)
                a[j--]=a[i];//高位替换
        }
        a[i]=index;
        sort(a,low,i-1);
        sort(a,i+1,hight);
    }
}
